package LeetCodeTest.PrimaryAlgorithmTest.LinkList;

public class MergeTwoLists {
    /**
     *合并两个有序链表
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * 示例 1：
     * 输入：l1 = [1,2,4], l2 = [1,3,4]
     * 输出：[1,1,2,3,4,4]
     * 示例 2：
     * 输入：l1 = [], l2 = []
     * 输出：[]
     * 示例 3：
     * 输入：l1 = [], l2 = [0]
     * 输出：[0]
     * 提示：
     * 两个链表的节点数目范围是 [0, 50]
     * -100 <= Node.val <= 100
     * l1 和 l2 均按 非递减顺序 排列
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnbp2/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public static void main(String[] args) {
        ListNode head5 = new ListNode(4);
        ListNode head4 = new ListNode(3,head5);
        ListNode list2 = new ListNode(1,head4);

        ListNode head2 = new ListNode(4);
        ListNode head1 = new ListNode(2,head2);
        ListNode list1 = new ListNode(1,head1);

        ListNode listNode = new MergeTwoLists().mergeTwoLists(list1, list2);

        ListNode temp = listNode;
        while (temp != null){
            System.out.println(temp.val);
            temp = listNode.next;
        }
    }

    /**
     * 思路1：因为链表是升序的，我们只需要遍历每个链表的头，比较一下哪个小就把哪个链表的头拿出来放到新的链表中，一直这样循环，直到有一个链表为空，然后我们再把另一个不为空的链表挂到新的链表中。
     * @return 合并后的链表
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null){
            return list2;
        }else if (list2 == null){
            return list1;
        }

        ListNode temp = new ListNode(0);
        ListNode current = temp;

        while (list1 != null && list2 != null){
            if (list1.val <= list2.val){
                current.next = list1;
                list1 = list1.next;
            }else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }

        current.next = (list1 == null ? list2 : list1);
        return temp.next;
    }
}
